package priv.conceit.study.leetcode.medium;

import java.util.*;

/**
 * 编号102
 * 二叉树的层次遍历
 * <a href="https://leetcode-cn.com/problems/binary-tree-level-order-traversal//"></a>
 * 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。。
 * <p>
 * 例如:
 * 给定二叉树: [3,9,20,null,null,15,7]
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回其层次遍历结果：
 * [[3],[9,20],[15,7]]
 * <p>
 * 1-队列
 * <p>
 * 2-递归
 * <p>
 * 时间复杂度：o(n) 每个节点都会被处理一次
 * 空间复杂度：o(n) 保存结果的数组 包含N个节点的值
 *
 * @author Conceit
 * @since 1.0.0, 2019/7/25
 */
public class BinaryTreeLevelOrderTraversal {

	public static void main(String[] args) {

	}

	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> result = new ArrayList<>();
		if (Objects.nonNull(root)) {
			//traversal(result, root);
			recursive(result,root,0);
		}
		return result;
	}


	/**
	 * 广度优先bfs
	 *
	 * @param result
	 * @param root
	 */
	public void traversal(List<List<Integer>> result, TreeNode root) {
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);

		while (!queue.isEmpty()) {

			//每一层的size
			int size = queue.size();
			List<Integer> layer=new ArrayList<>();

			for (int i = 0; i < size; i++) {
				TreeNode cur=queue.poll();
				layer.add(cur.val);

				if(Objects.nonNull(cur.left)){
					queue.offer(cur.left);
				}
				if(Objects.nonNull(cur.right)){
					queue.offer(cur.right);
				}
			}

			result.add(layer);
		}

	}

	/**
	 * 递归
	 *
	 * @param result
	 * @param root
	 * @param depth 层级 result.size=depth
	 */
	public void recursive(List<List<Integer>> result, TreeNode root,int depth){






















//		//当前 lists 的大小 小于该结点所在的层数，添加新的 list
//		if(result.size()==depth){
//			List<Integer> layer=new ArrayList<>();
//			result.add(layer);
//		}
//
//		result.get(depth).add(root.val);
//		if(Objects.nonNull(root.left)){
//			recursive(result,root.left,depth+1);
//		}
//		if(Objects.nonNull(root.right)){
//			recursive(result,root.right,depth+1);
//		}

	}
	public class TreeNode {

		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
}
